package com.exercises;

import com.alibaba.fastjson.JSONObject;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Exercise34 {
    public static void main(String[] args) {
        int nums[] = new int[]{0, 0, 1, 2, 2};
        int target = 0;
        System.out.println(JSONObject.toJSONString(new Exercise34().searchRange(nums, target)));
    }

    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 1) {
            return nums[0] == target ? new int[]{0, 0} : new int[]{-1, -1};
        } else if (nums.length > 1) {
            int start = -1, end = -1;
            if (nums[0] == target) {
                start = end = 0;
            } else if (nums[0] < target) {
                int i = 0, j = nums.length - 1;
                while (i <= j) {
                    int k = (i + j + 1) / 2;
                    if (nums[k] == target && nums[k - 1] < target) {
                        start = end = k;
                        break;
                    } else if (nums[k] < target) {
                        i = k + 1;
                    } else {
                        j = k - 1;
                    }
                }
            }

            if (start != -1) {
                if (nums[nums.length - 1] == target) {
                    end = nums.length - 1;
                } else {
                    int i = start, j = nums.length - 1;
                    while (i <= j) {
                        int k = (i + j) / 2;
                        if (nums[k] == target && nums[k + 1] > target) {
                            end = k;
                            break;
                        } else if (nums[k] > target) {
                            j = k - 1;
                        } else {
                            i = k + 1;
                        }
                    }
                }
            }
            return new int[]{start, end};
        }
        return new int[]{-1, -1};
    }
}
